package com.platform.modules.alg.alglib.poj3764;

public class Poj3764 {
    private int maxn = 100005;
    int n, mx; // n 个节点,最大值
    int trie[][]; //字典树存储的是01位
    int tot;
    int head[]; // 头结点
    int dx[] = new int[maxn]; // 从根到当前节点所有边权的 xor 值
    int cnt;

    Edge e[] = new Edge[maxn << 1];

    public String output = "";

    void add(int u, int v, int w) {
        e[++cnt].to = v;
        e[cnt].w = w;
        e[cnt].next = head[u];
        head[u] = cnt;
    }

    // 求 dx,从根到当前节点所有边权的 xor 值
    void dfs(int u, int f) {
        for (int i = head[u]; i > 0; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (v == f) // 父节点
                continue;
            dx[v] = dx[u] ^ w;
            dfs(v, u);
        }
    }

    void insert(int num) {
        int p = 1;
        for (int i = 30; i >= 0; i--) {
            int k = (num & (1 << i)) == 0 ? 0 : 1;
            if (trie[p][k] == 0)
                trie[p][k] = ++tot;
            p = trie[p][k];
        }
    }

    void init() {
        head = new int[maxn];
        trie = new int[maxn * 32][2];
        cnt = 0;
        tot = 1;
        mx = 0;
        for (int i = 0; i < e.length; i++) {
            e[i] = new Edge();
        }
    }

    int find(int num) {
        int p = 1, res = 0;
        for (int i = 30; i >= 0; i--) {
            int k = (num & (1 << i)) == 0 ? 0 : 1;
            if (trie[p][k ^ 1] != 0) { // 走相反路径
                res += 1 << i;
                p = trie[p][k ^ 1];
            } else
                p = trie[p][k];
        }
        return res;
    }

    public String cal(String input) {
        int u, v, w;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);
        init();
        for (int i = 1; i < n; i++) { // n-1 条边
            String[] words = line[i].split(" ");
            u = Integer.parseInt(words[0]);
            v = Integer.parseInt(words[1]);
            w = Integer.parseInt(words[2]);

            add(u + 1, v + 1, w);
            add(v + 1, u + 1, w);
        }
        dx[1] = 0;
        dfs(1, 0);
        insert(dx[1]);
        for (int i = 2; i <= n; i++) {
            mx = Math.max(mx, find(dx[i]));
            insert(dx[i]);
        }
        output += mx + "\n";
        return output;
    }
}

class Edge {
    int to, w, next;
}
